package netflow;

import java.io.*;
import java.util.*;
import java.text.*;
/*
 * @author deepthi
 */
public class FordFulkersonAlgo {
	
	public class VertexProperties {
		public boolean marked;
		public Edge edgeTo;
		public VertexProperties() {
		}
		public VertexProperties(boolean marked, Edge edgeTo) {
			this.marked = marked;
			this.edgeTo = edgeTo;
		}
	}
	private Map<String, VertexProperties> vertexValues;
	private Map<Edge, Double> edgeFlow;
    private double value;         // current value of max flow
  
    // max flow in flow network G from s to t
    public FordFulkersonAlgo(SimpleGraph SG) throws Exception {
    	
    	Vertex s = (Vertex)SG.vertexList.getFirst();
    	Vertex t = (Vertex)SG.vertexList.getLast();
    	
    	edgeFlow = new HashMap<Edge, Double>(SG.numEdges());
    	Iterator eI;
        for (eI = SG.edges();eI.hasNext();) {
        	Edge e = (Edge) eI.next();
        	edgeFlow.put(e, 0.0);
        }
       
        value = excess(SG, t);

        // while there exists an augmenting path, use it
        while (hasAugmentingPath(SG, s, t)) {

            // compute bottleneck capacity
            double bottle = Double.POSITIVE_INFINITY;
            for (Vertex v = t; (String)v.getName() != (String)s.getName();) {
            	Edge e = vertexValues.get((String)v.getName()).edgeTo;
            	double resV = residualCapacityTo(e, v);
                bottle = Math.min(bottle, resV);
                
                if((String)v.getName() == (String)e.getFirstEndpoint().getName())
                	v = e.getSecondEndpoint();
                else
                	v = e.getFirstEndpoint();
            }

            // augment flow
            for (Vertex v = t; (String)v.getName() != (String)s.getName();) {
            	Edge e = vertexValues.get((String)v.getName()).edgeTo;
                addResidualFlowTo(e, (String)v.getName(), bottle); 
                
                if((String)v.getName() == (String)e.getFirstEndpoint().getName())
                	v = e.getSecondEndpoint();
                else
                	v = e.getFirstEndpoint();
            }
            value += bottle;
        }
        
        System.out.println("Max flow is equal to "+value);

        // check optimality conditions
        System.out.println("checking whether max flow is equal to mincut - " + check(SG, s, t));
        assert check(SG, s, t);
    }

    // return value of max flow
    public double value()  {
        return value;
    }

    // is v in the s side of the min s-t cut?
    public boolean inCut(Vertex v)  {
        return vertexValues.get((String)v.getName()).marked;
    }


    // is there an augmenting path? 
    // if so, upon termination edgeTo[] will contain a parent-link representation of such a path
    private boolean hasAugmentingPath(SimpleGraph G, Vertex s, Vertex t) throws Exception {
    	vertexValues = new HashMap<String, VertexProperties>(G.numVertices());
    	Iterator vI;
    	for(vI = G.vertices(); vI.hasNext();) {
    		Vertex v = (Vertex) vI.next();
    		vertexValues.put((String)v.getName(), new VertexProperties(false, null));
    	}
        
        // breadth-first search
        Queue<Vertex> q = new LinkedList<Vertex>();
        q.offer(s);
        vertexValues.get((String)s.getName()).marked = true;
        while (!q.isEmpty()) {
            Vertex v = q.remove();
            
            Iterator eI;
            for (eI = v.incidentEdgeList.iterator();eI.hasNext();) {
            	Edge e = (Edge) eI.next();
            	
            	if((String)e.getFirstEndpoint().getName() == (String)v.getName()) {
            		Vertex w = e.getSecondEndpoint();

                    // if residual capacity from v to w
                    if (residualCapacityTo(e, w) > 0) {
                        if (!vertexValues.get((String)w.getName()).marked) {
                            vertexValues.get((String)w.getName()).edgeTo = e;
                            vertexValues.get((String)w.getName()).marked = true;
                            q.offer(w);
                            
                        }
                    }
            	}
            }
        }

        // is there an augmenting path?
        return vertexValues.get((String)t.getName()).marked;
    }
    
    private Double residualCapacityTo(Edge e, Vertex v) throws Exception {
    	String v1 = (String)v.getName();
    	if(v1 == (String)e.getFirstEndpoint().getName()) {
    		return edgeFlow.get(e);
    	}
    		
    	else if (v1 == (String)e.getSecondEndpoint().getName())
    		return ((Double)e.getData() - edgeFlow.get(e));
    	else 
    		throw new Exception("Illegal arugments");
    }
    private void addResidualFlowTo(Edge e, String vertex, double delta) throws Exception {
        if (vertex == (String)e.getFirstEndpoint().getName()) { 
        	double currentFlow = edgeFlow.get(e);
        	currentFlow -= delta;
        	edgeFlow.put(e, currentFlow);
        }
        else if (vertex == (String)e.getSecondEndpoint().getName()) { 
        	double currentFlow = edgeFlow.get(e);
        	currentFlow += delta;
        	edgeFlow.put(e, currentFlow);
        }
        else 
        	throw new Exception("Illegal arguments");
    }




    // return excess flow at vertex v
    private double excess(SimpleGraph G, Vertex v) {
       double excess = 0.0;
        //Edge e;
        Iterator eI;
        
        for(eI = v.incidentEdgeList.iterator(); eI.hasNext();) {
        	Edge e = (Edge) eI.next();
        	double flow = Double.parseDouble(e.getData().toString());
        	//Assuming getFirstEndPoint represents source vertex and 
        	//getSecondEndPoint represents destination vertex
            if (v.getName() == e.getFirstEndpoint().getName())
            	excess = excess -  flow;
            else
            	excess = excess + flow;
        }
        return excess;
    }


    // check optimality conditions
    private boolean check(SimpleGraph G, Vertex s, Vertex t) {

        // check that s is on the source side of min cut and that t is not on source side
        if (!inCut(s)) {
            System.err.println("source " + s + " is not on source side of min cut");
            return false;
        }
        if (inCut(t)) {
            System.err.println("sink " + t + " is on source side of min cut");
            return false;
        }

        // check that value of min cut = value of max flow
        double mincutValue = 0.0;
        Iterator i;
        for (i = G.vertices(); i.hasNext();) {
        	Vertex v = (Vertex) i.next();
        	
        	Iterator eI;
            for (eI = v.incidentEdgeList.iterator(); eI.hasNext();) {
            	Edge e = (Edge) eI.next();

            	boolean a = ((String)v.getName() == (String)e.getFirstEndpoint().getName());
            	boolean b = inCut(e.getFirstEndpoint());
            	boolean c = inCut(e.getSecondEndpoint());
            	
                if (a && b && !c)
                    mincutValue += (Double)e.getData();
            }
        }

        double EPSILON = 1E-11;
        if (Math.abs(mincutValue - value) > EPSILON) {
            System.err.println("Max flow value = " + value + ", min cut value = " + mincutValue);
            return false;
        }

        return true;
    }


	
public static void main (String args[]) {
    SimpleGraph SG =new SimpleGraph();
    GraphInput.LoadSimpleGraph(SG, "test.txt");


    Iterator i;
    Vertex v; Edge e;
    System.out.println("Iterating through vertices...");
    for (i= SG.vertices();i.hasNext() ; ) {
        v = (Vertex) i.next();
        System.out.println("found vertex " + v.getName());
        Iterator j;
        for (j = SG.incidentEdges(v); j.hasNext();) {
            e = (Edge) j.next();
            System.out.println("  found edge " + e.getData());
	        }
    }
    
    Iterator eI;
    for (eI = SG.edges();eI.hasNext();) {
    	Edge e1 = (Edge) eI.next();
    	//System.out.println(e1.getData());
    }
    
    try {
		new FordFulkersonAlgo(SG);
	} catch (Exception e1) {
		e1.printStackTrace();
	}
    
}}